// 09-排序2 Insert or Merge
#include <stdio.h>
#include <stdlib.h>
#define MaxSize 100

#define ElementType int

/* 基础工具(swap.c) =======================================*/

void swap(ElementType *a, ElementType *b) {
    ElementType t;
    t = *a;
    *a = *b;
    *b = t;
}

int comparator(ElementType a, ElementType b) {
    if (a > b) {
        return 1;
    } else if (a < b) {
        return -1;
    } else {
        return 0;
    }
}

// 打印空格分隔的，结尾无空格的数组
void printArray(int a[], int n) {
    if (n < 1 || a == NULL) {
        return;
    }
    printf("%d", *a++);
    for (int i=1; i<n; i++) {
        printf(" %d", *a++);
    }
}

void inputArray(int a[], int n) {
    for (int i=0; i<n; i++, a++) {
        scanf("%d", a);
    }
}

/* Insertion =====================================*/
// 从第 P 趟开始继续排
void insertion_Sort_Pass(ElementType a[], int p, int length) {
    ElementType tmp = a[p]; // 下一个待排序的数
    int i;
    for (i=p; i > 0 && comparator(a[i-1], tmp) > 0; i--) {
        a[i] = a[i-1]; // 移出空位
    }
    // 插入
    a[i] = tmp;
}

/* Merge =========================================*/
// 合并两个有序数组
void merge(ElementType a[], ElementType temp[], int leftStart, int rightStart, int rightEnd) {
    // 左边起点
    int left = leftStart;
    // 左边终点
    int leftEnd = rightStart - 1;
    // 右边起点
    int right = rightStart;
    // 临时数组的下标
    int tempIndex = leftStart;
    
    // 两个数组都有元素
    while (left <= leftEnd && right <= rightEnd) {
        if (comparator(a[left], a[right]) <= 0) {
            temp[tempIndex++] = a[left++];
        } else {
            temp[tempIndex++] = a[right++];
        }
    }
    // 左边有剩余
    while (left <= leftEnd) {
        temp[tempIndex++] = a[left++];
    }
    // 右边有剩余
    while (right <= rightEnd) {
        temp[tempIndex++] = a[right++];
    }
}

void merge_pass(ElementType a[], ElementType temp[], int length, int step) {
    int i;
    for (i=0; i < length - 2 * step; i += 2*step) {
        // 左边起点
        int leftStart = i;
        // 右边起点
        int rightStart = i + step;
        // 右边终点
        int rightEnd = i + 2*step - 1;
        // 合并
        merge(a, temp, leftStart, rightStart, rightEnd);
    }
    if (i + step < length) {
        // 归并最后2个子列
        merge(a, temp, i, i + step, length-1);
    } else {
        // 只剩下1个子列
        for (int j=i; j < length; j++) {
            temp[j] = a[j];
        }
    }
}


/* current =======================================*/
// 检查是否插入排序
// 前p个有序，后n-p个和原始序列一样
int isInsertion(int *base, int *sorted, int n) {
    int p;
    for (p=0; p<n; p++) {
        if (sorted[p] > sorted[p+1]) {
            break;
        }
    }
    int left;
    for (left=p+1; left < n; left++) {
        if (base[left] != sorted[left]) {
            break;
        }
    }
    if (left == n) {
        // 是insertion,返回执行了几次
        return p;
    } else {
        return 0;
    }
}

// 判断归并段的长度
int getStep(int *sorted, int n) {
    for (int step=2; step <= n; step *= 2) {
        // 检查(1,2),(3,4),...段是否有序，若有序 step *= 2 继续检查
        // 若无序，返回 step
        for (int i=1; i*step < n; i+=2) {
            int r = i*step;
            int l = r - 1;
            if (comparator(sorted[l], sorted[r]) > 0) {
                return step;
            }
        }
    }
    return n;
}

int main() {
    // 原始
    int base[MaxSize];
    // 排好序的
    int sorted[MaxSize];
    
    int n;
    scanf("%d", &n);

    inputArray(base, n);
    inputArray(sorted, n);

    int p = isInsertion(base, sorted, n);
    if (p != 0) {
        printf("Insertion Sort\n");
        insertion_Sort_Pass(sorted, p+1, n);
        printArray(sorted, n);
    } else {
        printf("Merge Sort\n");
        int step = getStep(sorted, n);
        // printf("step = %d\n", step);
        merge_pass(sorted, base, n, step);
        printArray(base, n);
    }

    return 0;
}
